#include <bits/stdc++.h>
using namespace std;

#define ONLINE_JUDGE

#ifndef ONLINE_JUDGE
#define dbg(x...)                             \
	{                                         \
		cerr << "\033[32;1m" << #x << " -> "; \
		err(x);                               \
	}
void err()
{
	cerr << "\033[39;0m" << endl;
}
template <typename T, typename... A>
void err(T a, A... x)
{
	cerr << a << ' ';
	err(x...);
}
#else
#define dbg(...)
#endif

typedef long long LL;

int t, r, c;
const int N = 255;
char mp[N][N];

int target[N * N], tcnt;
vector<int> G[N * N];

int id[N][N], x[N * N], y[N * N];
void build(char mp[N][N], int n, int m, vector<int> G[])
{
	auto pd = [&](int i, int j) {
		return i >= 0 && i < n && j >= 0 && j < m;
	};
	static const int dx[4] = {0, 0, 1, -1},
					 dy[4] = {1, -1, 0, 0};
	int tot = 0;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
		{
			id[i][j] = ++tot;
			x[tot] = i;
			y[tot] = j;
		}

	for (int i = 0; i <= tot + 1; ++i)
		G[i].clear();

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			for (int r = 0; r < 4; ++r)
			{
				int tx = i + dx[r], ty = j + dy[r];
				if (pd(tx, ty))
				{
					G[id[i][j]].push_back(id[tx][ty]);
				}
			}
		}
	}
}

int level[N * N];

void bfs(int s, int tot)
{
	queue<int> Q;
	Q.push(s);
	level[s] = 1;
	memset(level, 0, sizeof(int) * (tot + 1));
	while (!Q.empty())
	{
		int now = Q.front();
		Q.pop();
		for (int v : G[now])
		{
			if (level[v] == 0)
			{
				level[v] = level[now] + 1;
				Q.push(v);
			}
		}
	}
}

bool pd(int mid, int tot)
{
	static int t[N * N], tcnt;
	static vector<int> dat[N], dat2[N];
	tcnt = 0;
	for (int i = 0; i < tot; ++i)
	{
		if (level[target[i]] - 1 > mid)
		{
			t[tcnt++] = target[i];
		}
	}
	if (tcnt == 0)
		return true;
	for (int i = 0; i < r; ++i)
	{
		dat[i].clear();
	}
	for (int i = 0; i < c; ++i)
		dat2[i].clear();
	for (int i = 0; i < tcnt; ++i)
	{
		int xx = x[t[i]], yy = y[t[i]];
		dat[xx].push_back(t[i]);
		dat2[yy].push_back(t[i]);
	}
	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			int tans = 0;
			if (mp[i][j] == '1')
				continue;
			for (int k = 0; k < r; ++k)
			{
				if (!dat[k].size())
					continue;
				int id = *dat[k].begin();
				tans = max(tans, abs(i - k) + abs(j - y[id]));
				id = dat[k].back();
				tans = max(tans, abs(i - k) + abs(j - y[id]));
			}

			for (int k = 0; k < c; ++k)
			{
				if (!dat2[k].size())
					continue;
				int id = *dat2[k].begin();
				
				tans = max(tans, abs(j - k) + abs(i - x[id]));
				id = dat2[k].back();
				tans = max(tans, abs(j - k) + abs(i - x[id]));
			}
			if (tans <= mid)
			{
				return true;
			}
		}
	}
	return false;
}

int main(int argc, char const *argv[])
{
	scanf("%d", &t);
	for (int kk = 0; kk < t; ++kk)
	{
		scanf("%d%d", &r, &c);
		for (int i = 0; i < r; ++i)
			scanf("%s", mp[i]);

		build(mp, r, c, G);

		int s = r * c + 1;
		tcnt = 0;
		for (int i = 0; i < r; ++i)
		{
			for (int j = 0; j < c; ++j)
			{
				if (mp[i][j] == '0')
					target[tcnt++] = id[i][j];
				else
					G[s].push_back(id[i][j]);
			}
		}

		bfs(s, r * c + 1);

		for (int i = 0; i < r; ++i)
			for (int j = 0; j < c; ++j)
				dbg(i, j, id[i][j], level[id[i][j]]);

		int lb = -1, rb = r + c;
		dbg(lb, rb);
		while (lb < rb - 1)
		{
			int mid = (lb + rb) / 2;
			dbg(mid);
			if (pd(mid, tcnt))
				rb = mid;
			else
				lb = mid;
		}

		printf("Case #%d: %d\n", kk + 1, rb);
	}
	return 0;
}